#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    x=x*f;
    return x;
}
void write(long long x){
    if(x<0){
        x=-x;
        putchar('-');
    }
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
int t;
int n,a[200005];
int zz[20];
long long ans=-1,cnt;
int main(){
    freopen("color.in","r",stdin);
    freopen("color.out","w",stdout);
    t=read();
    while(t--){
        n=read();
        for(int i=1;i<=n;i++)a[i]=read();
        if(n<=15){
            for(int i=0;i<=n;i++){
                for(int j=1;j<=i;j++)zz[j]=1;
                for(int j=i+1;j<=n;j++)zz[j]=2;
                do{
                    for(int j=n;j>=1;j--){
                        for(int k=j-1;k>=1;k--){
                            if(zz[j]==zz[k]){
                                if(a[j]==a[k])cnt+=a[j];
                                break;
                            }
                        }
                    }
                    ans=max(ans,cnt);
                    cnt=0;
                }while(next_permutation(zz+1,zz+n+1));
            }
            write(ans);
            printf("\n");
            ans=0;
        }else{
            int rs=1;
            for(int i=1;i<=n;i++){
                for(int j=i+1;j<=n;j++){
                    if(zz[j]!=0)continue;
                    bool fl=0,f=0;
                    if(zz[i]!=0)fl=1;
                    if(a[i]==a[j]){
                        f=1;
                        if(zz[i]!=0){
                            zz[j]=zz[i];
                        }else{
                            zz[i]=rs;
                            zz[j]=rs;
                        }
                    }
                    if(f==1){
                        if(fl==1){
                            int k;
                            if(zz[i]==1)k=2;
                            else k=1;
                            for(int x=i+1;x<=j-1;x++){
                                if(zz[x]==0)zz[x]=k;
                            }
                        }else{
                            if(rs==1)rs=2;
                            else rs=1;
                            for(int x=i+1;x<=j-1;x++){
                                if(zz[x]==0)zz[x]=rs;
                            }
                        }
                        break;
                    }
                }
            }
            for(int j=n;j>=1;j--){
                for(int k=j-1;k>=1;k--){
                    if(zz[j]==zz[k]){
                        if(a[j]==a[k])cnt+=a[j];
                            break;
                    }
                }
            }
            ans=max(ans,cnt);
            cnt=0;
            ans=0;
            for(int i=1;i<=n;i++){
                ans+=a[i];
            }
            write(ans);
            printf("\n");
            ans=0;
        }
    }
    return 0;
}